package leetcode.hash;

public class KMPCopy {
    public static int indexOf(String str1, String str2) {

    if (str1==null && str2==null && str2.length()<1 && str1.length()<str2.length()){
        return -1;
    }

//    char[] arr1 = str1.toCharArray();
//    char[] arr2 = str2.toCharArray();
//    int i = 0;
//    int j = 0;
//    int[] next = getNextArray(arr2);
//
//    while (i<arr1.length && j<arr2.length){
//        if (arr1[i] == arr2[j]){
//            i++;
//            j++;
//        }else if (j==0){
//            i++;
//        }else {
//            j=next[j];
//        }
//    }
//    return j==arr2.length ? i-j : -1;
         char[] arr1 = str1.toCharArray();
         char[] arr2 = str2.toCharArray();
         int i =0;
         int j =0;
         int[] nextArray = getNextArray(arr2);
         while (i<arr1.length && j<arr2.length){
             if (arr1[i] == arr2[j]){
                 i++;
                 j++;
             }else if (j!=0){
                 j = nextArray[j];
             }else {
                 i++;
             }

         }
         return j == arr2.length?i-j : -1;
    }

    public static int[] getNextArray(char[] arr) {
        if (arr.length==1){
            return new int[]{-1};
        }

        int[] next = new int[arr.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int i =2;
      while (i<arr.length){
          if (arr[i-1] == arr[cn]){
              next[i++] = ++cn;
          }else if (cn!=0){
              next[cn] = cn;
          }else {
              next[i++] = 0;
          }
      }
      return next;
    }
//        if (arr.length == 1) {
//            return new int[]{-1};
//        }
//
//        int[] next = new int[arr.length];
//        next[0] = -1;
//        next[1] = 0;
//        int cn = 0;
//        int i = 2;
//
//        while (i < arr.length) {
//            if (arr[i - 1] == arr[cn]) {
//                next[i++] = ++cn;
//            } else if (cn != 0) {
//                cn = next[cn];
//            } else {
//                next[i++] = 0;
//            }
//        }
//        return next;
//    }
}
